package s9_树.tree1_二叉树;

/**
 * @author wisdomelon
 * @date 2020/7/30 0030
 * @project data_study
 * @jdk 1.8
 * 二叉树
 */
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();

        HeroNode root = new HeroNode("A", "A");
        HeroNode b = new HeroNode("B", "B");
        HeroNode c = new HeroNode("C", "C");
        HeroNode d = new HeroNode("D", "D");
        HeroNode e = new HeroNode("E", "E");
        HeroNode f = new HeroNode("F", "F");
        HeroNode g = new HeroNode("G", "G");

        root.setLeft(b);
        root.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);
        c.setRight(g);
        binaryTree.setRoot(root);


        /**
         *                A
         *          B           C
         *      D      E     F     G
         */

        System.out.println("----------------A B D E C F G--------------------");
        binaryTree.preOrder();
        System.out.println("----------------D B E A F C G--------------------");
        binaryTree.midOrder();
        System.out.println("----------------D E B F G C A--------------------");
        binaryTree.postOrder();

        HeroNode heroNode1 = binaryTree.preOrderSearch("D");
        System.out.println(heroNode1.toString());
        HeroNode heroNode2 = binaryTree.midOrderSearch("D");
        System.out.println(heroNode2.toString());
        HeroNode heroNode3 = binaryTree.postOrderSearch("D");
        System.out.println(heroNode3.toString());

        System.out.println("------------------------------------");
        binaryTree.delNode("D");
        binaryTree.midOrder();
        System.out.println("------------------------------------");
        binaryTree.delNode("C");
        binaryTree.midOrder();
        System.out.println("------------------------------------");
        binaryTree.delNode("Z");
        binaryTree.midOrder();
        System.out.println("------------------------------------");
    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }


    public void preOrder() {
        if(root == null) {
            throw new NullPointerException();
        }
        root.preOrder();
    }

    public void midOrder() {
        if(root == null) {
            throw new NullPointerException();
        }
        root.midOrder();
    }

    public void postOrder() {
        if(root == null) {
            throw new NullPointerException();
        }
        root.postOrder();
    }

    public HeroNode preOrderSearch(String no) {
        if(root == null) {
            return null;
        }
        return root.preOrderSearch(no);
    }

    public HeroNode midOrderSearch(String no) {
        if(root == null) {
            return null;
        }
        return root.midOrderSearch(no);
    }

    public HeroNode postOrderSearch(String no) {
        if(root == null) {
            return null;
        }
        return root.postOrderSearch(no);
    }

    public void delNode(String no) {
        if (root == null) {
            throw new NullPointerException();
        }
        if(root.getNo().equals(no)) {
            root = null;
            return;
        }
        root.delNode(no);
    }
}

class HeroNode {
    private String no;

    private String name;

    private HeroNode left;

    private HeroNode right;

    public HeroNode(String no, String name) {
        this.no = no;
        this.name = name;
    }

    public void setNo(String no) {
        this.no = no;
    }

    public String getNo() {
        return no;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroHode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历
     * 1.先输出当前节点（第一次为父节点）
     * 2.如果左子节点不为空，则递归继续前序遍历
     * 3.如果右子节点不为空，则递归继续前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if(this.left != null) {
            this.left.preOrder();
        }
        if(this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     * 1.如果当前节点的左子节点不为空，则递归继续中序遍历
     * 2.输出当前节点
     * 3.如果当前节点的右子节点不为空，则递归继续中序遍历
     */
    public void midOrder() {
        if(this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.midOrder();
        }
    }

    /**
     * 后序遍历
     * 1.如果当前节点的左子节点不为空，则递归继续后序遍历
     * 2.如果当前节点的右子节点不为空，则递归继续后序遍历
     * 3.输出当前节点
     */
    public void postOrder() {
        if(this.left != null) {
            this.left.postOrder();
        }
        if(this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }


    /**
     * 前序遍历查找
     * @param no 查找no
     * @return 如果找到就返回该Node，没找到就返回null
     */
    public HeroNode preOrderSearch(String no) {
        // 比较当前节点是不是
        if(this.no.equals(no)) {
            return this;
        }

        // 判断当前节点的左子节点是否为空，如不为空，则递归前序遍历查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode != null) {
            // 说明左子树找到了
            return resNode;
        }

        // 如果左子树没找到，判断当前节点的右子节点是否为空，如不为空，则递归前序遍历查找
        if(this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }


    /**
     * 中序遍历查找
     * @param no 查找no
     * @return 如果找到就返回该Node，没找到就返回null
     */
    public HeroNode midOrderSearch(String no) {
        // 判断当前节点的左子节点是否为空，如不为空，则递归中序遍历查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode != null) {
            // 说明左子树找到了
            return resNode;
        }

        // 比较当前节点是不是
        if(this.no.equals(no)) {
            return this;
        }

        // 如果左子树没找到，判断当前节点的右子节点是否为空，如不为空，则递归中序遍历查找
        if(this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }


    /**
     * 后序遍历查找
     * @param no 查找no
     * @return 如果找到就返回该Node，没找到就返回null
     */
    public HeroNode postOrderSearch(String no) {
        // 判断当前节点的左子节点是否为空，如不为空，则递归中序遍历查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode != null) {
            // 说明左子树找到了
            return resNode;
        }

        // 如果左子树没找到，判断当前节点的右子节点是否为空，如不为空，则递归中序遍历查找
        if(this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        if(resNode != null) {
            // 说明右子树找到了
            return resNode;
        }

        // 如果左右子树都没找到，比较当前节点是不是
        if(this.no.equals(no)) {
            resNode = this;
        }
        return resNode;
    }

    public void delNode(String no) {
        if(this.left != null && this.left.no.equals(no)) {
            this.left = null;
            return;
        }
        if(this.right != null && this.right.no.equals(no)) {
            this.right = null;
            return;
        }

        if(this.left != null) {
            this.left.delNode(no);
        }
        if(this.right != null) {
            this.right.delNode(no);
        }
    }

}
